package com.cqs.leetcode.math;

import java.util.Arrays;

public class PerfectSquares279 {


    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= i; j++) {
                int t = j * j;
                if (t > i || t < 0) break;
                min = Math.min(min, dp[i - t] + 1);
            }
            dp[i] = min;
        }
        return dp[n];
    }


    static class Solution {
        public int numSquares(int n) {
            int dp[] = new int[n + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            //依次求出 1, 2... 直到 n 的解
            for (int i = 1; i <= n; i++) {
                //依次减去一个平方数
                for (int j = 1; j * j <= i; j++) {
                    dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
                }
            }
            return dp[n];
        }

    }

    public static void main(String[] args) {
        System.out.println(Math.sqrt(Integer.MAX_VALUE));
        PerfectSquares279 perfectSquares279 = new PerfectSquares279();
        Solution sol = new Solution();
        for (int i = 4; i <= (1 << 22); i++) {
            int i1 = perfectSquares279.numSquares(i);
            int i2 = sol.numSquares(i);
            if (i1 != i2) {
                System.out.println(i + "\t" + i1 + "\t" + i2);
            }
            if (i % 1000 == 0) System.out.println(i);
        }
    }
}
